package Controller.DVNet;

import java.util.*;

// 全局需求
public class GlobalRequirement {
    NetworkSetting ns;
    Area startArea;
    Area endArea;
    Router startRouter;
    Router endRouter;
    ArrayList<Router> waypoints;
    ArrayList<Node> nodes;
    int maxLength;

    ArrayList<Stack<LinkState>> states;
    Set<Router> alreadyVisitedRouter;
    Map<Area, ArrayList<Node>> result;

    public GlobalRequirement(NetworkSetting networkSetting, String start, String end){
        this.ns = networkSetting;
        states = new ArrayList<>();
        alreadyVisitedRouter = new HashSet<>();
        waypoints = new ArrayList<>();
        nodes = new ArrayList<>();
        startRouter = ns.getRouter(start);
        endRouter = ns.getRouter(end);
        result = new HashMap<>();
        maxLength = 0;
        if(startRouter == null || endRouter == null){
            System.err.println("start or end router is not exists.");
            return;
        }

        startArea = startRouter.area;
        endArea = endRouter.area;
    }

    public void setWaypoint(String ... waypointsStr){
        waypoints.clear();
        for(String s: waypointsStr){
            Router r = ns.getRouter(s);
            if(r == null){
                System.err.println(s+"is not exists.");
                return;
            }
            waypoints.add(r);
        }
    }

    public void setMaxLength(int i){
        maxLength = i;
    }

    public void partition(){
        alreadyVisitedRouter.clear();
        nodes.clear();
        boolean r = dfs(0, startRouter,0, null);
        if(!r) System.out.println("no result");
    }

    private boolean dfs(int length, Router now, int waypointIndex, Node last){
        // check loop
        if(alreadyVisitedRouter.contains(now))
            return false;

        // check length
        if(maxLength >0 && length>maxLength)
            return false;

        boolean hasNext = false;
        Set<Router> visited = new HashSet<>();
        Node n = new Node(now);
        nodes.add(n);
        // update state
        alreadyVisitedRouter.add(now);

        // check finish
        if(now == endRouter && waypointIndex == waypoints.size()) {
            alreadyVisitedRouter.remove(now);
            n.isFinal = true;
            newEdge(last, n);
            return true;
        }

        // move to another router(waypoint or end router) in the current area
        if(waypointIndex < waypoints.size()){
            if(now == waypoints.get(waypointIndex)){
                waypointIndex++;
            }
            if(now.area == waypoints.get(waypointIndex).area){
                hasNext |= dfs(length+1, waypoints.get(waypointIndex), waypointIndex+1, n);
                visited.add(waypoints.get(waypointIndex));
            }
        }else {
            if (now.area == endArea) {
                hasNext |= dfs(length+1, endRouter, waypointIndex, n);
                visited.add(endRouter);
            }
        }

        // move to another area
        if (now.isBorder) {
            for (RouterPort rp : now.borderPorts) {
                if(!visited.contains(rp.linkPort.router)){
                    hasNext |= dfs(length+1, rp.linkPort.router, waypointIndex, n);
                    visited.add(rp.linkPort.router);
                }
            }
        }
        for (Router r : now.area.borderRouters) {
            if(r == endRouter || r == now || visited.contains(r)) continue;
            hasNext |= dfs(length+1, r, waypointIndex, n);
            visited.add(r);
        }

        // if has next node, save this node and create edge,
        if(hasNext){
            if(last != null)
                newEdge(last, n);
        }else{
            nodes.remove(n);
        }
        // reset state

        alreadyVisitedRouter.remove(now);
        return hasNext;
    }

    private void newEdge(Node from, Node to){
        from.next.add(to);
        to.prev.add(from);
    }

    public void genAbstractDVNet() {
//        nodes.sort(Comparator.comparingInt(n -> n.router.name.hashCode()));
        markIndexAndPrintNode();

        // merge end node
        for(int i=0;i< nodes.size();i++){
            Node node = nodes.get(i);
            if(node.isFinal && !node.deleteMark){
                for(int j=i+1;j<nodes.size();j++){
                    Node t_node = nodes.get(j);
                    if(t_node.router == node.router && t_node.isFinal){
                        t_node.deleteMark = true;
                        for(Node from:t_node.prev){
                            from.next.add(node);
                            from.next.remove(t_node);
                        }
                    }
                }
            }

        }
        // remove other end node
        nodes.removeIf(node -> node.deleteMark);

        markIndexAndPrintNode();

        ArrayList<Node> waitMerge = new ArrayList<>(nodes);


        boolean merge = true;
        while (merge){
            merge = false;
            for(int i=0;i<waitMerge.size();i++){
                Node node = waitMerge.get(i);
                if(node.deleteMark) continue;
                for(int j=i+1;j<waitMerge.size();j++){
                    Node jNode = waitMerge.get(j);
                    if(node.hasSameNext(jNode)){
                        merge = true;
                        jNode.deleteMark = true;
                        for(Node to:jNode.next){
                            node.next.add(to);
                            to.prev.remove(jNode);
                            to.prev.add(node);
                        }
                        for(Node from:jNode.prev){
                            node.prev.add(from);
                            from.next.remove(jNode);
                            from.next.add(node);
                        }
                    }
                }
            }
            nodes.removeIf(node -> node.deleteMark);
            waitMerge = new ArrayList<>(nodes);
        }

        for(int i=0;i<nodes.size();i++){
            nodes.get(i).index = i;
        }

        HashMap<Router, Integer> routerNodeIndex = new HashMap<>();
        for(Area area:ns.areaMap.values()){
            result.put(area, new ArrayList<>());
        }
        for(Router router:ns.routerMap.values()){
            routerNodeIndex.put(router, 0);
        }
        for(Node node:nodes){
            result.get(node.router.area).add(node);
            node.sameNodeIndex = routerNodeIndex.get(node.router);
            routerNodeIndex.computeIfPresent(node.router, (r, i)->i+1);
        }
    }

    private void markIndexAndPrintNode() {
        for(int i=0;i<nodes.size();i++){
            nodes.get(i).index = i;
        }
        for(Node node:nodes){
            System.out.printf("%s %s next:{%s} prev:{%s}\n", node.index, node.router.name, node.next, node.prev);
        }
    }

    public void showResult(){
        for(Area area:result.keySet()){
            ArrayList<Node> nodeList = result.get(area);
            nodeList.sort(Comparator.comparingInt(n -> n.router.name.hashCode()));
            System.out.println(area.name + ":");
            for(Node node:nodeList){
                System.out.printf(" %s-%s next:{", node.router.name, node.sameNodeIndex);
                for(Node to:node.next){
                    System.out.printf("%s-%s ", to.router.name, to.sameNodeIndex);
                }
                System.out.print("} prev:{");
                for(Node from:node.prev){
                    System.out.printf("%s-%s ", from.router.name, from.sameNodeIndex);
                }
                System.out.println("}");

            }

        }
    }

    public void calPath(){

    }

    public static void main(String[] args) {
        NetworkSetting ns = new NetworkSetting();

        ns.setArea("area1.properties", "S", "A");
        ns.setArea("area2", "B", "W", "C", "E", "F");
        ns.setArea("area3", "D", "J", "I");
        ns.setArea("area4", "G", "H");
        ns.setArea("area5", "K", "L");
        ns.addTopology("A", "B", "B", "A");
        ns.addTopology("C", "D", "D", "C");
        ns.addTopology("F", "K", "K", "F");
        ns.addTopology("L", "J", "J", "L");
        ns.addTopology("H", "I", "I", "H");
        ns.addTopology("E", "G", "G", "E");
        GlobalRequirement r = new GlobalRequirement(ns, "S", "D");
        r.setWaypoint("W");
        r.setMaxLength(5);

//        ns.setArea("area1.properties", "S", "A");
//        ns.setArea("area2", "B", "H", "C", "E");
//        ns.setArea("area3", "D");
//        ns.setArea("area4", "F", "G");
//        ns.addTopology("A", "0", "B", "0");
//        ns.addTopology("C", "0", "D", "0");
//        ns.addTopology("F", "0", "E", "0");
//        ns.addTopology("G", "0", "H", "0");
//        GlobalRequirement r = new GlobalRequirement(ns, "S", "D");
        r.partition();
        r.genAbstractDVNet();
        r.calPath();
        r.showResult();
    }


    private static class LinkState {
        public boolean isDirect;
        public Router router;

        public LinkState(boolean isDirect, Router router){
            this.isDirect = isDirect;
            this.router = router;
        }


        @Override
        public String toString() {
            return "{" + (isDirect?"direct":"abstract") + " " + router.name + '}';
        }
    }

    private static class Node{
        public Router router;
        public Set<Node> next;
        public Set<Node> prev;
        public boolean isFinal;
        public boolean deleteMark;
        public int index;
        public int sameNodeIndex;
        public Node(Router router){
            this.router = router;
            isFinal = false;
            deleteMark = false;
            next = new HashSet<>();
            prev = new HashSet<>();
        }

        public boolean hasSameNext(Node n){
            if(this.router != n.router) return false;
            if(n.next.size() != this.next.size()) return false;
            for(Node to:n.next){
                boolean flag = false;
                for(Node thisTo:this.next){
                    if(thisTo == to){
                        flag = true;
                        break;
                    }
                }
                if(!flag) return false;
            }
            return true;
        }

//        public boolean hasNextEdge(Edge edge){
//            for(Edge nextEdge: next){
//                if(nextEdge.isDirect == edge.isDirect && nextEdge.to == edge.to){
//                    return true;
//                }
//            }
//            return false;
//        }
//
//        public boolean hasPrevEdge(Edge edge){
//            for(Edge prevEdge: prev){
//                if(prevEdge.isDirect == edge.isDirect && prevEdge.from == edge.from){
//                    return true;
//                }
//            }
//            return false;
//        }

        @Override
        public String toString() {
            StringBuilder sb = new StringBuilder();
//            sb.append(router.name).append(": next{");
//            for(Node to:next){
//                sb.append(to.router.name).append(",");
//            }
//            sb.append("} ");
            sb.append(index).append(router.name);

            return sb.toString();
        }
    }

//    private static class Edge{
//        public boolean isDirect;
//        public Node from;
//        public Node to;
//
//        public Edge(Node from, Node to, boolean isDirect){
//            this.from = from;
//            this.to = to;
//            this.isDirect = isDirect;
//            from.next.add(this);
//            to.prev.add(this);
//        }
//
//        @Override
//        public String toString() {
//            return String.format("(%s %s.%s -> %s.%s)", (isDirect?"direct":"abstract"), from.index, from.router.name,
//                    to.index, to.router.name);
//        }
//    }
}

